#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int countSubmatrices(vector<vector<int>>& grid, int k) {
        int n=grid.size();
        int m=grid[0].size();
        vector<vector<int>> vec(n+1,vector<int>(m+1));
        int count=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                vec[i][j]=vec[i-1][j]+vec[i][j-1]-vec[i-1][j-1]+grid[i-1][j-1];
                if(vec[i][j]<=k) count++;
            }
        }
        return count;
        
    }
};

int main()
{
    vector<vector<int>> vec={{7,6,3},{6,6,1}};
    Solution so;
    so.countSubmatrices(vec,18);
    return 0;
}